/*
 * @lc app=leetcode id=464 lang=cpp
 *
 * [464] Can I Win
 */

// @lc code=start
class Solution {
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        n = maxChoosableInteger;
        if (maxChoosableInteger >= desiredTotal) {
            return true;
        }
        if ((maxChoosableInteger + 1) * maxChoosableInteger /2 < desiredTotal) {
            return false;
        }
        return canWin(desiredTotal, 0);
    }
    bool canWin(int target, int visited) {
        auto iter = table.find(visited);
        if (iter != table.end()) {
            return iter->second;
        }
        for (int i = 1; i <= n; ++i) {
            int mask = (1 << i);
            if ((mask & visited) == 0 && (i >= target || canWin(target-i, mask | visited) == false)){
                table[visited] = true;
                return true;
            }          
            
        }
        table[visited] = false;
        return false;

    }
    int n;
    unordered_map<int, bool> table;
};
// @lc code=end

